#include <iostream>
#include <string.h>
using namespace std;

struct node{
	int data;
	node *lchr,*rchr;
};


class BT
{
	
	public:
		BT()
		{
			head=NULL;
		}
		~BT(){
			dest(head);
		}
		void dest(node *p){
			if(p!=NULL){
				dest(p->lchr);
				dest(p->rchr);
				delete p;
			}
			else {
				delete p;
				return ;
			}
		}
		void creatTree(node *&p,int k);
		node *head;
		//int count;
		void visit(node *t);
		void preorder(node *p);
		void inorder(node *p);
		void lastorder(node *p);
};

void BT::creatTree(node *&p,int k)
{
	if(p==NULL) {
		p=new node();
		p->data=k;
		p->lchr=NULL;
		p->rchr=NULL;
		return ;
	}
	else if(p->data>k){
		creatTree(p->lchr,k);
	}
	
	else if(k>p->data){
		creatTree(p->rchr,k);
	}
	else return ;
}

void BT::visit(node *t){
	if(t!=NULL){
		cout<<t->data<<" ";
			return ;
		
	}
	else {
		return ;
	}
}

void BT::preorder(node *p){
	if(p==NULL) return ;
	else {
		visit(p);
		preorder(p->lchr);
		preorder(p->rchr);
	}
}

void BT::inorder(node *p){
	if(p==NULL) return ;
	else {
		inorder(p->lchr);
		visit(p);
		inorder(p->rchr);
	}
}

void BT::lastorder(node *p)
{
	if(p==NULL) return ;
	else {
		lastorder(p->lchr);
		lastorder(p->rchr);
		visit(p);
	}
}






int a[101];
//int chongfu[101];
//int jishu=0;

int main()
{
	int n;
	while(cin>>n){
		BT myTree;
		//memset(chongfu,0,sizeof(chongfu));
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		for(int i=0;i<n;i++){
			myTree.creatTree(myTree.head,a[i]);
		}
		myTree.preorder(myTree.head);
		cout<<endl;
		//jishu=0;
		myTree.inorder(myTree.head);
		cout<<endl;
		//jishu=0;
		myTree.lastorder(myTree.head);
		cout<<endl;
		//jishu=0;
	}
	
	return 0;
	
}











